package com.wyp168.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @ClassName PermuteSolution
 * @Title leetcode 46.全排列
 * @Description TODO  给定一个数组nums，返回所有重新排列的集合List
 * @Author wyp168
 * @Date 2022/10/19 19:13
 */
public class PermuteSolution {
    public static void main(String[] args) {
        PermuteSolution solution = new PermuteSolution();
        int[] nums = {1,1,2};
        List<List<Integer>> permute = solution.permute(nums);
        for (List<Integer> integers : permute) {
            System.out.println(integers);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        int ns = nums.length;
        Deque<Integer> deque = new ArrayDeque<>();
        List<List<Integer>> resultList = new ArrayList<>();
        dfs(nums, ns, deque, resultList);
        return resultList;
    }

    public void dfs(int[] nums, int length, Deque<Integer> deque, List<List<Integer>> resultList) {
        //判断递归出口
        if (deque.size() == length) {
            resultList.add(new ArrayList<>(deque));
            return;
        }

        for (int num : nums) {
            if (deque.contains(num))
                continue;
            deque.addLast(num);
            dfs(nums, length, deque, resultList);
            deque.removeLast();
        }
    }
}
